package com.base.leetcode;

import com.base.dataStructure.heap.Heap;
import com.sun.scenario.effect.impl.prism.PrImage;

import java.util.PriorityQueue;

/**
 * @Author: hdhao
 * @Create: 2023/4/5 - 14:55
 * @Version: v1.0
 */
//求数据流的中位数(使用两个堆来解决)
@SuppressWarnings("all")
public class Leetcode295_2 {
    /*
        为了保证两个堆中数据量的平衡(当新来数据时)
            两边个数一样时,左边个数加一
            两边个数不一样时,右边个数加一
        但是,随便一个数能直接加入吗？
            左边个数加一时,应该挑右边最小的加入
            右边个数加一时,应该挑左边最大的加入
     */
    public void addNum(int num) {
        if (left.size() == right.size()) {
            right.offer(num);
            left.offer(right.poll());
        } else {
            left.offer(num);
            right.offer(left.poll());
        }
    }
    public double findMedian() {
        if (left.size() == right.size()) {
            return (left.peek() + right.peek()) / 2.0;
        }else {
            return left.peek();
        }
    }
    private PriorityQueue<Integer> left = new PriorityQueue<>(
            (a,b)->Integer.compare(b,a)
    );
    private PriorityQueue<Integer> right = new PriorityQueue<>();

}
